package com.cat.chapter054;
/**
 * @author cat
 * @description https://leetcode.cn/problems/sliding-window-maximum/description/
 * @create 2025/7/25 15:43
 * @since JDK17
 */

public class Solution01 {
    static int N = ((int) (1e5 + 10));
    static int[] dequee = new int[N];
    public int[] maxSlidingWindow(int[] nums, int k) {
        int h = 0, t = 0, n = nums.length;
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < k - 1; i++) {
            while (h < t && nums[dequee[t - 1]] <= nums[i]) {
                t--;
            }
            dequee[t++] = i;
        }

        for (int i = k - 1, l = 0; i < n; i++, l++) {
            while (h < t && nums[dequee[t - 1]] <= nums[i]) {
                t--;
            }
            dequee[t++] = i;
            ans[l] = nums[dequee[h]];
            if (i - k + 1 == dequee[h]) h++;
        }

        return ans;
    }
}

